package 力扣91;

/**
 * @ClassName : Day11_142_环形链表II
 * @Author : 骆发茂
 * @Date: 2021/12/22 21:46
 * @Description : https://leetcode-cn.com/problems/linked-list-cycle-ii/
 * 思路：慢指针移动两步，快指针移动一步，相遇之后，快指针变成头指针，然后每次快慢指针各走一步直到相遇，相遇的节点就是入环节点
 * 复杂度：时间复杂度O(n)，空间复杂度O(1)
 *https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/shuang-zhi-zhen-dong-hua-tu-jie-dai-ma-j-b1fc/
 * 作者：chen-wei-f
 * 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/shuang-zhi-zhen-dong-hua-tu-jie-dai-ma-j-b1fc/
 */
public class Day11_142_环形链表II_快慢指针 {
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode slow = head, fast = head;
            while (fast != null) {
                slow = slow.next;
                if (fast.next != null) {
                    fast = fast.next.next;
                } else {
                    return null;
                }
                if (fast == slow) {
                    ListNode fast1 = head;
                    while (fast1 != slow) {
                        fast1 = fast1.next;
                        slow = slow.next;
                    }
                    return fast1;
                }
            }
            return null;
        }
    }
}